// 斐波那契数列
// 1 1 2 3 5 8 13

// 爬楼梯问题，实际就是求斐波那契数列，可以使用最简单的递归，但是数字过大时会超出时间限制，在leetcode上无法通过
function dp(n) {
    if (n === 1) {
        return 1
    } else if (n === 2) {
        return 2
    } else {
        return dp(n - 1) + dp(n - 2)
    }
}

// const res =  dp(45)

// 可以使用备忘录方法，记录下每次F(n)的值
// 时间复杂度为O(n), 空间复杂度也为O(n)
// 这也不是最优的算法，可以用两个变量代替数组，使得空间复杂度为O(1)
function dp1(n) {
    if (n === 1) {
        return 1
    } else if (n === 2) {
        return 2
    } else if (n > 2) {
        const arr = [1, 2]
        for (let i = 2; i < n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2]
        }
        return arr[n - 1]
    }
}
const res = dp1(45)
console.log(res)